/**
 * 分而治之的方式, 就是声明两个数组, 给一个provit, 大于这个provit就放左边, 否则放右边. 
 * 
 */


let array = [1, 89, 0, 29, 11, 111, 798, 90]
 function quickSort(arr) {
     let length = arr.length
     if(length <= 1) return arr


     let index = Math.floor(length / 2);
     let provit = arr.splice(index, 1)[0]
     length -= 1
     let leftArr = [], rightArr= []

     for (let i= 0; i< length-1 ; i++) {
         if(arr[i]< provit){
             leftArr.push(arr[i])
         }else {
             rightArr.push(arr[i])
         }
     }
     return quickSort(leftArr).concat([provit], quickSort(rightArr))
 }

let res = quickSort(array)
console.log(res);